package monotonic_stack;
import offer.Class04;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;
public class Class42 {
    //    Deque stack = new LinkedList<>();
//        stack.push(0);
//    int[]  result=new int[temperatures.length];
//        for (int i = 1; i < temperatures.length ; i++) {
//        while (!stack.isEmpty()&&temperatures[i]>temperatures[(int) stack.peek()]){
//            result[(int) stack.peek()]=i-(int)stack.pop();
//        }
//        stack.push(i);
//    }
//        return  result;
    public int trap(int[] height) {
        int sum = 0;
        Deque stack = new LinkedList<>();
        stack.push(height[0]);
        for (int i = 1; i < height.length; i++) {
            if (height[i] <= (int) stack.peek()) {
                stack.push(height[i]);
            } else {
                while (!stack.isEmpty() && height[i] > (int) stack.peek()) {
                    int right = height[i];
                }
            }
        }
        return sum;
    }
    public int trap1(int[] height) {
        int size = height.length;
        if (size <= 2) return 0;
        // in the stack, we push the index of array
        // using height[] to access the real height
        Stack<Integer> stack = new Stack<Integer>();
        stack.push(0);
        int sum = 0;
        for (int index = 1; index < size; index++) {
            int stackTop = stack.peek();
            if (height[index] < height[stackTop]) {
                stack.push(index);
            } else if (height[index] == height[stackTop]) {
                // 因为相等的相邻墙，左边一个是不可能存放雨水的，所以pop左边的index, push当前的index
                stack.pop();
                stack.push(index);
            } else {
                //pop up all lower value
                int heightAtIdx = height[index];
                while (!stack.isEmpty() && (heightAtIdx > height[stackTop])) {
                    int mid = stack.pop();
                    if (!stack.isEmpty()) {
                        int left = stack.peek();
                        int h = Math.min(height[left], height[index]) - height[mid];
                        int w = index - left - 1;
                        int hold = h * w;
                        if (hold > 0) sum += hold;
                        stackTop = stack.peek();
                    }
                }
                stack.push(index);
            }
        }
        return sum;
    }
//TODO:2023/8/3  默写的
    public int trap2(int[] height) {
        if (height.length<= 2) return 0;
        int sum = 0;
        Deque stack = new LinkedList<Integer>();
        stack.push(0);
        for (int index = 1; index < height.length; index++) {

            if (height[index] < height[(int) stack.peek()]) {
                stack.push(index);
            } else if (height[index] == height[(int) stack.peek()]) {
                stack.pop();
                stack.push(index);
            } else {
                while (!stack.isEmpty() && height[index] >  height[(int) stack.peek()]) {
                 //TODO:2023/8/3 pop之后能排除栈中只有一个元素时 不能构成凹槽的情况
                    int mid = (int) stack.pop();
                    if (!stack.isEmpty()) {
                        int left = (int) stack.peek();
                        int h = Math.min(height[left], height[index]) - height[mid];
                        int w = index - left - 1;
                        int hold=h*w;
                        if (hold>0){
                            sum += h * w;

                        }
//                        stacktop=(int)stack.peek();
                    }
                }
                stack.push(index);
            }
        }
        return sum;
    }

    public static void main(String[] args) {

        Class42 class42 = new Class42();
        int[] arr={0,1,0,2,1,0,1,3,2,1,2,1};
        System.out.println(class42.trap1(arr));
        System.out.println(class42.trap2(arr));


    }
}